//
// Created by francklinson on 2021/5/25.
//
/**
 * 同104
 */
#include <iostream>

using namespace std;
// Definition for a binary tree node.

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int maxDepth(TreeNode *root) {
        return dfs(root, 0);
    }

    int dfs(TreeNode *root, int depth) {
        if (root == nullptr) return depth;
        int leftDepth = dfs(root->left, depth + 1);
        int rightDepth = dfs(root->right, depth + 1);
        return max(leftDepth, rightDepth);
    }
};

int main() {
    auto n1 = TreeNode(3), n2 = TreeNode(9), n3 = TreeNode(20), n4 = TreeNode(5), n5 = TreeNode(7);
    n1.left = &n2;
    n1.right = &n3;
    n3.left = &n4;
    n3.right = &n5;
    Solution sol;
    cout << sol.maxDepth(&n1) << endl;
    return 0;

}